//https://leetcode.cn/problems/restore-ip-addresses/description/
//1.典型的backstack实现；2.使用了stoi对异常进行了捕获判断；

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> res_str_vec;
    bool isValid(std::string str){
        try{
            if(str.size()>1&& str[0]=='0'){
                return false;
            }
            int num=std::stoi(str);
            
            if(num>255){
                return false; 
            }
            return true;
        }catch(std::exception& EXC){
            return false;
        }
    }
    void dfs(const string& s,int start,int circle,std::vector<string>& cur_str_vec){
        if(4==circle){
            if(start!=s.size()){
                return;
            }
            std::string tmp_str="";
            for(auto item:cur_str_vec){
                tmp_str=tmp_str+item+".";
            }
            tmp_str.pop_back();
            res_str_vec.push_back(tmp_str);
            std::cout<< tmp_str << std::endl;
            return;
        }
        for(size_t i=start;i<start+3&&i<s.size();++i){
            std::string cur_string =s.substr(start,i-start+1);
            if(isValid(cur_string)){
                cur_str_vec.emplace_back(cur_string);
                dfs(s,i+1,circle+1,cur_str_vec);
                cur_str_vec.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.empty()) return {};
        int start=0,circel=0;
        std::vector<string> cur_str_vec;
        dfs(s,start,circel,cur_str_vec);
        return res_str_vec;
    }
};